{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sort Characters By Frequency"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #bucket-sort #counting #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #桶排序 #计数 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: frequencySort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #根据字符出现频率排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串 <code>s</code> ，根据字符出现的 <strong>频率</strong> 对其进行 <strong>降序排序</strong> 。一个字符出现的 <strong>频率</strong> 是它出现在字符串中的次数。</p>\n",
    "\n",
    "<p>返回 <em>已排序的字符串&nbsp;</em>。如果有多个答案，返回其中任何一个。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s = \"tree\"\n",
    "<strong>输出: </strong>\"eert\"\n",
    "<strong>解释: </strong>'e'出现两次，'r'和't'都只出现一次。\n",
    "因此'e'必须出现在'r'和't'之前。此外，\"eetr\"也是一个有效的答案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s = \"cccaaa\"\n",
    "<strong>输出: </strong>\"cccaaa\"\n",
    "<strong>解释: </strong>'c'和'a'都出现三次。此外，\"aaaccc\"也是有效的答案。\n",
    "注意\"cacaca\"是不正确的，因为相同的字母必须放在一起。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s = \"Aabb\"\n",
    "<strong>输出: </strong>\"bbAa\"\n",
    "<strong>解释: </strong>此外，\"bbaA\"也是一个有效的答案，但\"Aabb\"是不正确的。\n",
    "注意'A'和'a'被认为是两种不同的字符。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 5 * 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code>&nbsp;由大小写英文字母和数字组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sort-characters-by-frequency](https://leetcode.cn/problems/sort-characters-by-frequency/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sort-characters-by-frequency](https://leetcode.cn/problems/sort-characters-by-frequency/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"tree\"', '\"cccaaa\"', '\"Aabb\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums, key = lambda x : (nums.count(x), -x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt=Counter(nums)\n",
    "        nums.sort(key=lambda x:(cnt[x],-x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums, key=lambda x: (nums.count(x), -x))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        s=Counter(nums)\n",
    "        nums.sort(key=lambda x: (s[x], -x))\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        counter = Counter(nums)\n",
    "        return sorted(nums,key=lambda x: (counter[x],-x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        d = {}\n",
    "        for num in nums:\n",
    "            if num in d:\n",
    "                d[num] += 1\n",
    "            else:\n",
    "                d[num] = 1\n",
    "        res = []\n",
    "        for i in d:\n",
    "            res.append([d[i], -i])\n",
    "        res.sort()\n",
    "        ans = []\n",
    "        for r in res:\n",
    "            ans += [-r[1]] * r[0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        dict={}\n",
    "        for num in nums:\n",
    "            if num in dict:\n",
    "                dict[num]+=1\n",
    "            else:\n",
    "                dict[num]=1\n",
    "        sorted_nums = sorted(nums, key=lambda x: (dict[x], -x))\n",
    "        return sorted_nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        a = defaultdict(int)\n",
    "\n",
    "        for i in nums:\n",
    "            a[i]+=1\n",
    "\n",
    "        res = [(key, val) for key, val in a.items()]\n",
    "        res.sort(key=lambda x:(x[1], -x[0]))\n",
    "        # print(res)\n",
    "        out = []\n",
    "        for tup in res:\n",
    "            out+=[tup[0]]*tup[1]\n",
    "\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nums.sort(key=lambda x:(cnt[x],-x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums, key=lambda x:(nums.count(x), -x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nums.sort(key=lambda x: (cnt[x], -x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        freq=Counter(nums)\n",
    "        nums.sort(key=lambda x:(freq[x],-x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        c = collections.Counter(nums)\n",
    "        nums.sort(key=lambda x: (c[x], -x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        return sorted(nums, key=lambda x: (cnt[x], -x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums,key=lambda x: (nums.count(x),-x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nums.sort(key=lambda x: (cnt[x], -x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        counter = Counter(nums)\n",
    "        return sorted(nums,key=lambda x: (counter[x],-x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        dic =  Counter(nums)\n",
    "        nums.sort(key = lambda x: (dic[x], -x))\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nums.sort(key=lambda x: (cnt[x], -x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        c = Counter(sorted(nums))\n",
    "        res = []\n",
    "        for x in c.most_common():\n",
    "            res.extend([x[0]] * x[1])\n",
    "        return list(reversed(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        c = Counter(nums)\n",
    "        nums.sort(key = lambda n:(c[n], -n))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nums.sort(key=lambda x: (cnt[x], -x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nums.sort(key=lambda x:(cnt[x], -x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt= Counter(nums)\n",
    "        nums.sort(key = lambda x:(cnt[x],-x))\n",
    "        return nums\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        a = Counter(nums)\n",
    "        nums.sort(key=lambda x:(a[x],-x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nums.sort(key=lambda x: (cnt[x], -x))\n",
    "        return nums\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        m={}\n",
    "        for i in nums:\n",
    "            if m.get(i)==None:\n",
    "                m[i]=0\n",
    "            m[i]+=1\n",
    "        nums=sorted(nums,key=lambda x:(m[x],-x))\n",
    "        \n",
    "        return nums\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nums.sort(key=lambda x: (cnt[x], -x))\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        freq_dict = {}\n",
    "        for num in nums:\n",
    "            freq_dict[num] = freq_dict.get(num, 0) + 1\n",
    "        res = sorted(nums, key = lambda x: (freq_dict[x], -x))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        dic = Counter(nums)\n",
    "        def custom_sort(item):\n",
    "            return dic[item], -item\n",
    "        nums.sort(key = custom_sort)\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        c = Counter(nums)\n",
    "        frequency_dictionary = dict()\n",
    "        for key, value in c.items():  # 循环体部分可以使用collections.defaultdict优化（可以省去判断部分）\n",
    "            if value in frequency_dictionary.keys():\n",
    "                frequency_dictionary[value].append(key)\n",
    "            else:\n",
    "                frequency_dictionary[value] = [key]\n",
    "        # print(frequency_dictionary)\n",
    "\n",
    "        ans = list()\n",
    "        # print(sorted(frequency_dictionary))\n",
    "        for num in sorted(frequency_dictionary):  # 按字典中的键的升序顺序取出其对应值（数据类型: 列表）的各元素\n",
    "            frequency_dictionary[num].sort(reverse = True)  # 将字典的各值中的元素降序排列\n",
    "            for number in frequency_dictionary[num]:\n",
    "                ans.extend([number] * num)  # 将每个数乘以出现次数后添加到 ans 中\n",
    "        return ans\n",
    "'''\n",
    "  输入: nums = [-1,2,-6,4,5,-6,3,4,3,-6,-4,5,8,3,-1,-2,9,7]\n",
    "  标准输出:\n",
    "    {2: [-1, 4, 5], 1: [2, -4, 8, -2, 9, 7], 3: [-6, 3]}\n",
    "    [1, 2, 3]\n",
    "  输出: [9,8,7,2,-2,-4,5,5,4,4,-1,-1,3,3,3,-6,-6,-6]\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        num_frequency = Counter(nums)\n",
    "\n",
    "        value_count = collections.defaultdict(list)\n",
    "        for key, value in num_frequency.items():\n",
    "            value_count[value].append(key)\n",
    "        \n",
    "        result = []\n",
    "        for key in sorted(value_count.keys()):\n",
    "            if len(value_count[key]) > 1:\n",
    "                for i in sorted(value_count[key], reverse=True):\n",
    "                    result += [i] * key\n",
    "            else:\n",
    "                result += [value_count[key][0]] * key\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums):\n",
    "        return sorted(nums, key=lambda x: (nums.count(x), -x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums,key=lambda x:(nums.count(x),-x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums,key=lambda x: (nums.count(x),-x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        # return sorted(nums, key = lambda n: (nums.count(n), -n) )\n",
    "        cnt = Counter(nums)\n",
    "        return sorted(nums, key = lambda n: (cnt[n], -n))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        count = Counter(nums)\n",
    "        arr = []\n",
    "        for k, v in count.items():\n",
    "            arr.append([k, v])\n",
    "        arr.sort(key=lambda x: (x[1], -x[0]))\n",
    "        res = []\n",
    "        for a in arr:\n",
    "            res.extend([a[0] for _ in range(a[1])])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums, key = lambda x:(nums.count(x), -x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nums.sort(key=lambda x: (cnt[x], -x))\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        counter = Counter(nums)\n",
    "        return sorted(nums,key=lambda x: (counter[x],-x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        fMap = defaultdict(int)\n",
    "        for num in nums:\n",
    "            fMap[num] += 1\n",
    "        nums.sort(key=lambda x: (fMap[x], -x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nums.sort(key=lambda x: (cnt[x], -x))\n",
    "        return nums\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        freq = []\n",
    "        for num in nums:\n",
    "            freq.append(nums.count(num))\n",
    "        ans = sorted(zip(freq, nums), key = lambda x: (x[0], -x[1]))\n",
    "\n",
    "        return list(map(lambda x: x[1], ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nums.sort(key = lambda x:(cnt[x],-x))\n",
    "        return nums\n",
    "        # cc= sorted(cnt.items(),key = lambda x:x[1])\n",
    "        # ans = []\n",
    "        # for k,c in cc:\n",
    "        #     ans.extend([k]*c)\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        arr = [[] for i in range(101)]\n",
    "        cur = 0\n",
    "        dic = collections.Counter(nums)\n",
    "        for k,v in dic.items():\n",
    "            arr[v].append(k)\n",
    "        for i in range(101):\n",
    "            if arr[i]:\n",
    "                arr[i].sort(reverse=True)\n",
    "                for num in arr[i]:\n",
    "                    while dic[num] > 0:\n",
    "                        nums[cur] = num\n",
    "                        cur += 1\n",
    "                        dic[num] -= 1\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        return sorted(nums, key=lambda x: (cnt[x], -x))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        coun = Counter(nums)\n",
    "        nums.sort(key = lambda x:(coun[x],-x))\n",
    "        return nums\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        count=dict()\n",
    "        for num in nums:\n",
    "            if num not in count:\n",
    "                count[num]=0\n",
    "            else:\n",
    "                count[num]+=1\n",
    "        lst1=[]\n",
    "        for key,val in count.items():\n",
    "            lst1.append((val,key))\n",
    "        for i in range(len(lst1)-1):\n",
    "            for j in range(len(lst1)-i-1):\n",
    "                if lst1[j][0]>lst1[j+1][0]:\n",
    "                    lst1[j],lst1[j+1]=lst1[j+1],lst1[j]\n",
    "                if lst1[j][0]==lst1[j+1][0] and lst1[j][1]<lst1[j+1][1]:\n",
    "                    lst1[j],lst1[j+1]=lst1[j+1],lst1[j]\n",
    "        lst2=[]\n",
    "        for i in lst1:\n",
    "            lst2.append((i[1],i[0]))\n",
    "        output=[]\n",
    "        for i in lst2:\n",
    "            for j in range(i[1]+1):\n",
    "                output.append(i[0])\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums,key=lambda x: (nums.count(x),-x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        h=[0]*201\n",
    "        for num in nums:\n",
    "            h[num+100]+=1\n",
    "        nums.sort(key=lambda x:(h[x+100],-x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        dic =  Counter(nums)\n",
    "        nums.sort(key = lambda x: (dic[x], -x))\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums,key=lambda x: (nums.count(x),-x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "\n",
    "        nums.sort(key=lambda x:  (cnt[x], -x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums, key = lambda x: (mp[x],-x) if (mp:=Counter(nums)) else nums) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums, key = lambda x: (Counter(nums)[x],-x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        count = {}\n",
    "        for num in nums:\n",
    "            if num in count:\n",
    "                count[num] += 1\n",
    "            else:\n",
    "                count[num] = 1\n",
    "        \n",
    "        numsList = [num for num in count]\n",
    "        numsList.sort(key = lambda x: (count[x], -x))\n",
    "        \n",
    "        res = []\n",
    "        for num in numsList:\n",
    "            res += [num] * count[num]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def frequencySort(self, nums):\n",
    "        m=Counter(nums)\n",
    "        r=list(sorted(m.items(),key=lambda item:(item[1],-item[0])))\n",
    "        res=[]\n",
    "        for i,j in r:\n",
    "            for _ in range(j):\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        dic = Counter(nums)\n",
    "        lst = sorted([(-k, v) for k, v in dic.items()], key=lambda n: (n[1], n[0]))\n",
    "        ans = []\n",
    "        for k, v in lst:\n",
    "            ans += [-k] * v\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        l = sorted(list(cnt.items()), key=lambda x: (x[1],-x[0]))\n",
    "        x = []\n",
    "        for (k,freq) in l:\n",
    "            x += [k]*freq\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        m = dict()\n",
    "        for num in nums:\n",
    "            if -num in m:\n",
    "                m[-num] += 1\n",
    "            else:\n",
    "                m[-num] = 1\n",
    "        m = sorted(m.items(), key = lambda x: (x[1], x[0]))\n",
    "        res = []\n",
    "        for num, freq in m:\n",
    "            res += [-num]*freq\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def frequencySort(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        import collections as c\n",
    "        dict_nums = c.Counter(nums)\n",
    "\n",
    "        dict_nums = sorted(dict_nums.items(), key=lambda  x: (x[1], -x[0]))\n",
    "        dict_nums = dict(dict_nums)\n",
    "        nums = []\n",
    "        for key, value in dict_nums.items():\n",
    "            for i in range(int(value)):\n",
    "                nums.append(int(key))\n",
    "        return nums\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        listall=[]\n",
    "        for c in range(1,len(nums)+1):\n",
    "            list=[]\n",
    "            for i in nums:\n",
    "                if nums.count(i)==c:\n",
    "                    list.append(i)\n",
    "            list.sort()\n",
    "            list.reverse()\n",
    "            listall.extend(list)\n",
    "            del(list)\n",
    "        return listall\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        check={}\n",
    "        for digit in nums:\n",
    "            if digit in check:\n",
    "                check[digit]+=1\n",
    "            else:\n",
    "                check[digit]=1\n",
    "        # res=[]\n",
    "        # while check:\n",
    "        #     max_key=min(check,key=check.get)\n",
    "        #     val=check[max_key]\n",
    "        #     for _ in range(val):\n",
    "        #         res.append(max_key)\n",
    "        #     del check[max_key]\n",
    "        nums.sort(key=lambda x: (check[x], -x))\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "\n",
    "        check = collections.Counter(nums)\n",
    "\n",
    "        arrs = [x for x in check]\n",
    "        arrs = sorted(arrs, key = lambda x: [check[x],-x])\n",
    "\n",
    "        ans = []\n",
    "        for x in arrs:\n",
    "            ans += [x]*check[x]\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "         return sorted(nums, key = lambda x: (Counter(nums)[x],-x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        a = defaultdict(int)\n",
    "\n",
    "        for i in nums:\n",
    "            a[i]+=1\n",
    "\n",
    "        res = [(key, val) for key, val in a.items()]\n",
    "        res.sort(key=lambda x:(x[1], -x[0]))\n",
    "        print(res)\n",
    "        out = []\n",
    "        for tup in res:\n",
    "            out+=[tup[0]]*tup[1]\n",
    "\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        freq = []\n",
    "        for num in nums:\n",
    "            freq.append([nums.count(num),num * (-1)])\n",
    "        freq.sort()\n",
    "        res = [f[1] * (-1) for f in freq]\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        h = {}\n",
    "        for i in nums:\n",
    "            if i in h:\n",
    "                h[i] += 1\n",
    "            else:\n",
    "                h[i] = 1\n",
    "        nums.sort(key=lambda x:(h[x], -x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        hashdict = Counter(nums)\n",
    "        nums.sort(key = lambda x :(hashdict[x], -x))\n",
    "        return nums\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        dic =  Counter(nums)\n",
    "        nums.sort(key = lambda x: (dic[x], -x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums,key=lambda x: (nums.count(x),-x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        d = Counter(nums)\n",
    "        return sorted(nums,key= lambda x : [d[x],-x])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        m = collections.Counter(nums)\n",
    "\n",
    "        nums.sort(key=  lambda x: (m.get(x), -x))\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nf = [(num, freq) for num, freq in cnt.items()]\n",
    "        nf.sort(key=lambda x: (x[1], -x[0]))\n",
    "        ans = []\n",
    "        for num, freq in nf:\n",
    "            ans += [num] * freq\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from dataclasses import dataclass\n",
    "from heapq import heapify, heappop\n",
    "from typing import Dict, List\n",
    "\n",
    "\n",
    "@dataclass\n",
    "class CharCount:\n",
    "    char: str\n",
    "    count: int\n",
    "\n",
    "\n",
    "    def __eq__(self, other: \"CharCount\") -> bool:\n",
    "        return self.str == other.str and self.count == other.count\n",
    "    \n",
    "    \n",
    "    def _before(self, other: \"CharCount\") -> bool:\n",
    "        return (\n",
    "            self.count > other.count\n",
    "            or (self.count == other.count and ord(self.char) < ord(other.char))\n",
    "        )\n",
    "    \n",
    "    \n",
    "    def __lt__(self, other: \"CharCount\") -> bool:\n",
    "        return self._before(other)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        freq: Dict[char, int] = Counter(s)\n",
    "        max_heap: List[CharCount] = [\n",
    "            CharCount(char, count) for char, count in freq.items()\n",
    "        ]\n",
    "\n",
    "        heapify(max_heap)\n",
    "        n_uniqs: int = len(max_heap)\n",
    "        ans: List[CharCount] = [\n",
    "            heappop(max_heap) for i in range(n_uniqs)\n",
    "        ]\n",
    "            \n",
    "        return \"\".join(\n",
    "            (cc.char * cc.count) for cc in ans\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: 'str') -> 'str':\n",
    "        # Approach one\n",
    "        dic = {}\n",
    "        for i in s:\n",
    "            dic[i] = dic.get(i,0) + 1 \n",
    "        t = ''\n",
    "        for i,j in sorted([ (i ,j) for i, j in dic.items()], key = lambda x : x[1] , reverse = True):\n",
    "            t += i * j\n",
    "        return t\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return \"\".join([char * times for char, times in collections.Counter(s).most_common()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def frequencySort(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        s_counter = Counter(s)\n",
    "        # print(s_counter)\n",
    "        s_value_dict = dict()\n",
    "        res = ''\n",
    "        for key,value in s_counter.items():\n",
    "            s_value_dict[value] = s_value_dict.get(value, '') + key\n",
    "        for key in sorted(s_value_dict.keys(), reverse = True):\n",
    "            for letter in s_value_dict[key]:\n",
    "                res += key * letter\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        dict1 = {}\n",
    "        for i in s:\n",
    "            if i in dict1:\n",
    "                dict1[i] += 1\n",
    "            else:\n",
    "                dict1[i] = 1\n",
    "        z = zip(dict1.values(), dict1.keys())\n",
    "        r = sorted(z, reverse=True)\n",
    "        res = ''\n",
    "        for l, k in r:\n",
    "            for j in range(l):\n",
    "                res += k\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        dic={}\n",
    "        for i in s:\n",
    "            if i in dic:\n",
    "                dic[i]+=1\n",
    "            else:\n",
    "                dic[i]=1\n",
    "        lst=dic.items()\n",
    "        return \"\".join([a*b for a,b in sorted(lst,key=lambda x:-x[1])])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        counter = Counter(s)\n",
    "        buckets = [None] * len(s)\n",
    "        for word, count in counter.items():\n",
    "            if not buckets[count - 1]:\n",
    "                buckets[count - 1] = []\n",
    "            buckets[count - 1].append(word * count)\n",
    "        buckets.reverse()\n",
    "        return ''.join(''.join(bucket) for bucket in buckets if bucket)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        dic = dict()\n",
    "        dic1 = dict()\n",
    "        for i in s:\n",
    "            dic[i] = dic.get(i,0)+1\n",
    "        for i in dic:\n",
    "            dic1[dic[i]] = dic1.get(dic[i],[])+[i]\n",
    "        k = sorted(dic1.keys(),reverse=True)\n",
    "        res = []\n",
    "        for i in k:\n",
    "            for a in dic1[i]:\n",
    "                res.extend([a]*i)\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "想了半天，这个问题关键还在于用hash储存吧\n",
    "不然光计数都是O(m^2),m是不同元素个数\n",
    "\n",
    "还是这样吧，ran一下，然后一边计数一边插入排序\n",
    "'''\n",
    "from random import randint\n",
    "class freq:\n",
    "    def __init__(self, ch, freq):\n",
    "        self.c = ch\n",
    "        self.f = freq\n",
    "        \n",
    "class Solution:\n",
    "    def frequencySort(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        show = []\n",
    "        lst = list(s)\n",
    "        self.rand_lst(lst)\n",
    "        while len(lst):\n",
    "            n = len(lst)\n",
    "            new = lst[0]\n",
    "            lst = [ch for ch in lst if ch!=new]\n",
    "            new_node = freq(new, n - len(lst))\n",
    "            ## insert sort\n",
    "            show = [new_node] + show\n",
    "            for i in range(len(show)-1):\n",
    "                if show[i].f >= show[i+1].f:\n",
    "                    break\n",
    "                else:\n",
    "                    show[i], show[i+1] = show[i+1], show[i]\n",
    "                    \n",
    "        result = []\n",
    "        for node in show:\n",
    "            result += [node.c]*node.f\n",
    "        return \"\".join(result)\n",
    "                \n",
    "    def rand_lst(self, l):\n",
    "        n = len(l)\n",
    "        for i in range(n):\n",
    "            t = randint(i, n-1)\n",
    "            l[i], l[t] = l[t], l[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq as hq\n",
    "class Solution:\n",
    "    def frequencySort(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        d = {}\n",
    "        heap = []\n",
    "        for c in s:\n",
    "            d[c] = d.get(c, 0) + 1\n",
    "        for k, v in d.items():\n",
    "            hq.heappush(heap, (v, k))\n",
    "        ans = []\n",
    "        while(len(heap)>0):\n",
    "            k, v = hq.heappop(heap)\n",
    "            for i in range(k):\n",
    "                ans.append(v)\n",
    "        return ''.join(ans[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if len(s) <= 0:\n",
    "            return \"\"\n",
    "        temp_dict = {}\n",
    "        for item in s:\n",
    "            temp_dict[item] = temp_dict.get(item, 0) + 1\n",
    "        temp_list = [0] * (max(list(temp_dict.values())) + 1)\n",
    "        for key, value in temp_dict.items():\n",
    "            if isinstance(temp_list[value], list):\n",
    "                temp_list[value].append(key)\n",
    "            else:\n",
    "                temp_list[value] = [key]\n",
    "        result_list = []\n",
    "        for index in range(1, len(temp_list)):\n",
    "            if isinstance(temp_list[index], list):\n",
    "                for item in temp_list[index]:\n",
    "                    result_list.extend([item] * index)\n",
    "        return \"\".join(reversed(result_list))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        from collections import Counter\n",
    "        c=Counter(s)\n",
    "        string=''.join(sorted(c.elements(),key=c.get,reverse = True))\n",
    "        return string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: 'str') -> 'str':\n",
    "        char2Freq = dict(collections.Counter(s))\n",
    "        freq2Chars = {}\n",
    "        for c, f in char2Freq.items():\n",
    "            if f in freq2Chars.keys():\n",
    "                freq2Chars[f].append(c)\n",
    "            else:\n",
    "                freq2Chars[f] = [c]\n",
    "        sortedFreq = sorted(freq2Chars.keys(), reverse = True)\n",
    "        ans = ''\n",
    "        for f in sortedFreq:\n",
    "            for c in freq2Chars[f]:\n",
    "                ans += c * f\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        d = {}\n",
    "        res = \"\"\n",
    "        for c in s:\n",
    "            if not c in d:\n",
    "                d[c] = 1\n",
    "            else:\n",
    "                d[c] += 1\n",
    "        d = sorted(d.items(),key=lambda item:item[1],reverse=True)\n",
    "        for item in d:\n",
    "            res += item[0]*item[1]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        from collections import Counter\n",
    "        c=Counter(s)\n",
    "        result=''\n",
    "        for ch,times in c.most_common():\n",
    "            result+=ch*times\n",
    "        return result\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        dic = {}\n",
    "        for i in s:\n",
    "            if i not in dic:\n",
    "                dic[i] = s.count(i)\n",
    "        list1 = sorted(dic.items(), key=lambda x: x[1], reverse=True)\n",
    "        res = []\n",
    "        for i in list1:\n",
    "            res.append(i[0] * i[1])\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        dic = {}\n",
    "        res = ''\n",
    "        for i in s:\n",
    "            if i in dic:\n",
    "                dic[i] += 1\n",
    "            else:\n",
    "                dic[i] = 1\n",
    "        #dic[i] = dic.get(i,0)+1  和6-9一个意思\n",
    "        while dic: #max(dic)返回字典中最大的Key值\n",
    "            tmp = max(dic, key=dic.get) \n",
    "            print('tmp',tmp) #max(dic,key=dic.get)返回字典中最大值values对应的key\n",
    "            res += tmp*dic[tmp]\n",
    "            dic.pop(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        dict = collections.Counter(s).most_common()\n",
    "        str1 = ''\n",
    "        for i,j in dict:\n",
    "            str1 += i * j\n",
    "        return str1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        count = Counter(s)\n",
    "        count = sorted(count.items(),key=lambda x:x[1],reverse=True)\n",
    "        ans = ''\n",
    "        for ch,val in count:\n",
    "            ans += ch*val\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def frequencySort(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        hashmap = {}\n",
    "        for ans in s:\n",
    "            if ans not in hashmap:\n",
    "                hashmap[ans] = 1\n",
    "            else:\n",
    "                hashmap[ans] += 1\n",
    "        result = sorted(hashmap.items(),key=lambda hashmap:hashmap[1],reverse=True)\n",
    "        s = ''\n",
    "        for i in range(len(result)):\n",
    "            res = result[i][0] * result[i][1]\n",
    "            s += res\n",
    "        return s \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        hashmap = {}\n",
    "        for c in s:\n",
    "            hashmap[c] = hashmap.get(c, 0) +1\n",
    "        result = sorted(hashmap.items(), key = lambda hashmap: hashmap[1], reverse = True)\n",
    "        \n",
    "        s = ''\n",
    "        for i in range(len(result)):\n",
    "            res = result[i][0] * result[i][1]\n",
    "            s += res\n",
    "        \n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        dic = Counter(s)\n",
    "        frequent=dict() #key为频率 value为值\n",
    "        for key,value in dic.items():\n",
    "            if value in frequent:\n",
    "                frequent[value].append(key)\n",
    "            else:\n",
    "                frequent[value] = [key]\n",
    "        res = []\n",
    "        for i in range(len(s),0,-1):\n",
    "            if i in frequent: #key\n",
    "                for x in frequent[i]:\n",
    "                    res.append(x*i)\n",
    "        return \"\".join(res)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        dict_ = {}\n",
    "        ans = ''\n",
    "        for _ in s:\n",
    "            if _ in dict_.keys():\n",
    "                dict_[_] += 1\n",
    "            else:\n",
    "                dict_[_] = 1\n",
    "        while len(ans) != len(s):\n",
    "            for k, v in dict_.items():\n",
    "                if v == max(dict_.values()):\n",
    "                    ans += k * v\n",
    "                    dict_[k] = 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        s = Counter(s)\n",
    "\n",
    "        items = [(-v, k) for k, v in s.items()]\n",
    "\n",
    "        items = sorted(items)\n",
    "        \n",
    "        res = ''\n",
    "        for v, k in items:\n",
    "            res = res + ''.join(-v * k)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        counter = collections.defaultdict(int)\n",
    "        for i in s:\n",
    "            counter[i] += 1\n",
    "        res = ''\n",
    "        # 将字典排序\n",
    "        sort_counter = dict(sorted(counter.items(), key=lambda x: -x[1]))\n",
    "        for k in sort_counter.keys():\n",
    "            res += k * sort_counter[k]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        dict= {}\n",
    "        list = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in dict.keys():\n",
    "                dict[s[i]] += 1\n",
    "            else:\n",
    "                dict[s[i]] = 1\n",
    "        list = sorted(dict.items(), key = lambda x : x[1], reverse = True)\n",
    "        s=''\n",
    "        for i in list:\n",
    "            s += i[1] * i[0]\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        dicts = {}\n",
    "        count = 0\n",
    "        for i in s:\n",
    "            temp = dicts.get(i, 0)\n",
    "            dicts[i] = temp + 1\n",
    "            count = max(count, temp + 1)\n",
    "        path = [\"\" for i in range(count+1)]\n",
    "        for k, v in dicts.items():\n",
    "            path[v] += k * v\n",
    "        path.reverse()\n",
    "        return(\"\".join(path))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "      sList = list(s)\n",
    "      freq = {}\n",
    "      result = \"\"\n",
    "\n",
    "      for char in sList:\n",
    "        freq[char] = freq.get(char,0)+1\n",
    "      \n",
    "      pq = []\n",
    "      for key,value in freq.items():\n",
    "        pq.append((value,key))\n",
    "      pq.sort(reverse=True)\n",
    "\n",
    "      for value, key in pq:\n",
    "        tmp = key*value\n",
    "        result += tmp\n",
    "      \n",
    "      return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        cnt_mapping = Counter(s)\n",
    "        seq = sorted([(k, v) for k, v in cnt_mapping.items()], key=lambda x: x[1], reverse=True)\n",
    "        res = []\n",
    "        for k, v in seq:\n",
    "            res.extend([k for _ in range(v)])\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        dic = {}\n",
    "        res = []\n",
    "        for i in s:\n",
    "            dic[i] = dic.get(i, 0) + 1\n",
    "        sorted_dic = sorted(dic.items(), key=lambda x: x[1], reverse=True)\n",
    "        for i, v in sorted_dic:\n",
    "            for j in range(v):\n",
    "                res.append(i)\n",
    "        return \"\".join(res) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        table = collections.defaultdict(int)\n",
    "        order = []\n",
    "        res = []\n",
    "        for char in s:\n",
    "            table[char] += 1\n",
    "        for char, count in table.items():\n",
    "            heapq.heappush(order, (-count, char))\n",
    "        while order:\n",
    "            count, char = heapq.heappop(order)\n",
    "            count = -count\n",
    "            for _ in range(count):\n",
    "                res.append(char)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        cnt = {}\n",
    "        for i in s:\n",
    "            cnt[i] = cnt.get(i, 0) + 1\n",
    "        hq = []\n",
    "        for key, freq in cnt.items():\n",
    "            heapq.heappush(hq, (freq, key))\n",
    "        res = []\n",
    "        for _  in range(len(hq)):\n",
    "            freq, key = heappop(hq)\n",
    "            res.extend([key] * freq)\n",
    "        return \"\".join(res[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        cmap = {}\n",
    "        for i in range(len(s)):\n",
    "            freq = cmap.get(s[i], 0)\n",
    "            cmap[s[i]] = freq + 1\n",
    "\n",
    "        import heapq\n",
    "        data = []\n",
    "        for k, v in cmap.items():\n",
    "            heapq.heappush(data, (v, k))\n",
    "        ret = []\n",
    "        while data:\n",
    "            item = heapq.heappop(data)\n",
    "            i = 0\n",
    "            while i < item[0]:\n",
    "                ret.append(item[1])\n",
    "                i += 1\n",
    "        ans = ''.join(ret[::-1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        hash = {}\n",
    "        for i in s:\n",
    "            if i in hash:\n",
    "                hash[i] += 1\n",
    "            else:\n",
    "                hash[i] = 1\n",
    "        strout = sorted(sorted(s),key=lambda x:hash[x])\n",
    "        return ''.join(reversed(strout))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        order=sorted(list(set(s)),key=lambda x:s.count(x),reverse=True)\n",
    "        s=sorted(list(s),key=lambda x:order.index(x))\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        dic = {}\n",
    "        for i in s:\n",
    "            dic[i] = dic.get(i, 0) + 1\n",
    "        lst = sorted(sorted(list(s)), key=lambda x:dic[x], reverse=True)\n",
    "        return ''.join(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        \n",
    "        freqs = collections.defaultdict(int)\n",
    "        maxFreq = 0\n",
    "        \n",
    "        for ch in s:\n",
    "            freqs[ch] += 1\n",
    "            maxFreq = max(maxFreq, freqs[ch])\n",
    "        \n",
    "        bucket = [[] for i in range(maxFreq+1)]\n",
    "        for ch, freq in freqs.items():\n",
    "            bucket[freq].append(ch)\n",
    "\n",
    "        res = ''\n",
    "        for freq in range(maxFreq, -1, -1):\n",
    "            for ch in bucket[freq]:\n",
    "                res += ch * freq\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        \n",
    "        freqs = collections.defaultdict(int)\n",
    "        maxFreq = 0\n",
    "        \n",
    "        for ch in s:\n",
    "            freqs[ch] += 1\n",
    "            maxFreq = max(maxFreq, freqs[ch])\n",
    "        \n",
    "        bucket = [[] for i in range(maxFreq+1)]\n",
    "        for ch, freq in freqs.items():\n",
    "            bucket[freq].append(ch)\n",
    "\n",
    "        res = ''\n",
    "        for freq in range(maxFreq, -1, -1):\n",
    "            for ch in bucket[freq]:\n",
    "                res += ch * freq\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        freq = {}\n",
    "        for c in s:\n",
    "            if c in freq:\n",
    "                freq[c] += 1\n",
    "            else:\n",
    "                freq[c] = 1\n",
    "        max_freq = max(freq.values())\n",
    "        bucket = [[] for _ in range(max_freq)]\n",
    "        for key in freq.keys():\n",
    "            bucket[freq[key] - 1].append(key)\n",
    "        res = []\n",
    "        for i in range(max_freq - 1, -1, -1):\n",
    "            if len(bucket[i]):\n",
    "                for c in bucket[i]:\n",
    "                    res.extend(c * (i + 1))\n",
    "        return \"\".join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        mp = dict()\n",
    "        max_freq = 0\n",
    "        for char in s:\n",
    "            mp[char] = mp.get(char, 0) + 1\n",
    "            max_freq = max(max_freq, mp[char])\n",
    "\n",
    "        buckets = [None for _ in range(max_freq)]\n",
    "        for i in range(max_freq):\n",
    "            buckets[i] = []\n",
    "\n",
    "        for key, freq in mp.items():\n",
    "            buckets[freq - 1].append(key)\n",
    "\n",
    "        res = list()\n",
    "        for i in range(max_freq, -1, -1):\n",
    "            for char in buckets[i - 1]:\n",
    "                res.extend(char * i)\n",
    "\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        char_count=defaultdict(int)\n",
    "        max_freq=0\n",
    "\n",
    "        for char in s:\n",
    "            char_count[char]+=1\n",
    "            max_freq=max(max_freq,char_count[char])\n",
    "        \n",
    "        buckets = [[] for _ in range(max_freq + 1)]\n",
    "        for char,freq in char_count.items():\n",
    "            buckets[freq].append(char)\n",
    "        ret=[]\n",
    "\n",
    "        for freq in range(max_freq,0,-1):\n",
    "            for char in buckets[freq]:\n",
    "                ret.extend([char]*freq)\n",
    "        return ''.join(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        cnt = collections.Counter(s)\n",
    "        def f(ch1,ch2):\n",
    "            if cnt[ch1]<cnt[ch2]:\n",
    "                return 1\n",
    "            elif cnt[ch1]>cnt[ch2]:\n",
    "                return -1\n",
    "            else:\n",
    "                return 1 if ch1>ch2 else -1\n",
    "        st = list(s)\n",
    "        return ''.join(sorted(st,key=functools.cmp_to_key(f)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        freq = {}\n",
    "        for c in s:\n",
    "            if c not in freq:\n",
    "                freq[c] = 0\n",
    "            freq[c] += 1\n",
    "        return ''.join(sorted(s, key=lambda x:-freq[x] - 0.001*ord(x)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        freq = {}\n",
    "        for c in s:\n",
    "            if c not in freq:\n",
    "                freq[c] = 0\n",
    "            freq[c] += 1\n",
    "        return ''.join(sorted(s, key=lambda x:-freq[x] - 0.001*ord(x)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        cnt = Counter(s)\n",
    "        ss = sorted(list(s), key=lambda x:cnt[x]*100+ord(x), reverse=True)\n",
    "        return ''.join(ss)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        d = {}\n",
    "        s = list(s)\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in d.keys():\n",
    "                d[s[i]] = 1\n",
    "            else:\n",
    "                d[s[i]] += 1\n",
    "        def check(a,b):\n",
    "            if d[a] < d[b]:\n",
    "                return 1\n",
    "            else:\n",
    "                return -1\n",
    "        s.sort(key=cmp_to_key(check))\n",
    "        ans = \"\"\n",
    "        print(s)\n",
    "        s = list(set(s))\n",
    "        s.sort(key=cmp_to_key(check))\n",
    "        print(s)\n",
    "        for i in s:\n",
    "            ans += i*d[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        d = {}\n",
    "        s = list(s)\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in d.keys():\n",
    "                d[s[i]] = 1\n",
    "            else:\n",
    "                d[s[i]] += 1\n",
    "        def check(a,b):\n",
    "            if d[a] < d[b]:\n",
    "                return 1\n",
    "            else:\n",
    "                return -1\n",
    "        s.sort(key=cmp_to_key(check))\n",
    "        ans = \"\"\n",
    "        print(s)\n",
    "        s = list(set(s))\n",
    "        s.sort(key=cmp_to_key(check))\n",
    "        print(s)\n",
    "        for i in s:\n",
    "            ans += i*d[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        from collections import defaultdict\n",
    "        dict = defaultdict()\n",
    "        for i in s:\n",
    "            dict[i] = dict.get(i, 0) + 1\n",
    "        frequency = [[] for _ in range(len(s) + 1)]\n",
    "        for key, v in dict.items():\n",
    "            if v > 0:\n",
    "                frequency[v] += key\n",
    "        result = \"\"\n",
    "        for i in range(len(frequency) - 1, -1, -1):\n",
    "            for j in frequency[i]:\n",
    "                for _ in range(i):\n",
    "                    result += j\n",
    "        return result\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def frequencySort(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        frequency_letter = {}\n",
    "        for letter in s:\n",
    "            if letter in frequency_letter:\n",
    "                frequency_letter[letter] = frequency_letter[letter] + 1\n",
    "            else:\n",
    "                frequency_letter[letter] = 1\n",
    "        \n",
    "        buckets = [[] for _ in range(len(s)+1)]\n",
    "        for letter, frequency in frequency_letter.items():\n",
    "            buckets[frequency].extend(letter)\n",
    "        \n",
    "        ss = ''\n",
    "        for i in range(len(s),0,-1):\n",
    "            for j in buckets[i]:\n",
    "                ss = ss + j * i\n",
    "        return str(ss)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        y=Counter(s)\n",
    "        return \"\".join(sorted(s,key= lambda x:(y[x],x),reverse=True))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        freq={}\n",
    "        for ch in s:\n",
    "            if ch not in freq:\n",
    "                freq[ch]=1\n",
    "            else:\n",
    "                freq[ch]+=1\n",
    "        length=len(s)+1\n",
    "        freqlist=[[] for _ in range(length)]\n",
    "        for ch in freq:\n",
    "            freqlist[freq[ch]].append(ch)\n",
    "        ans=''\n",
    "        for i in range(length):\n",
    "            if freqlist[length-i-1] is not None:\n",
    "                for j in range(len(freqlist[length-i-1])):\n",
    "                    ans+=freqlist[length-i-1][j]*(length-i-1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        dt = {}\n",
    "        for c in s:\n",
    "            if c in dt:\n",
    "                dt[c] += 1\n",
    "            else:\n",
    "                dt[c] = 1\n",
    "        \n",
    "        bucket_lt = [[] for _ in range(len(s) + 1)]\n",
    "        for num in dt:\n",
    "            bucket_lt[dt[num]].append(num)\n",
    "        res = ''\n",
    "        for i in range(len(bucket_lt)-1, -1, -1):\n",
    "            if len(bucket_lt[i]) > 0:\n",
    "                for c in bucket_lt[i]:\n",
    "                    res += c * i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        count = {}\n",
    "        li = []\n",
    "        for c in s:\n",
    "            li.append(c)\n",
    "            count[c] = count.get(c, 0) + 1\n",
    "        li.sort(key=lambda c:(count[c], c), reverse=True)\n",
    "        return ''.join(li)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        cnt = {}\n",
    "        for char in s:\n",
    "            if char not in cnt:\n",
    "                cnt[char] = 0\n",
    "            cnt[char] += 1\n",
    "\n",
    "        all_freq = [[] for _ in range(len(s) + 1)]\n",
    "\n",
    "        for item, freq in cnt.items():\n",
    "            all_freq[freq].append(item)\n",
    "        \n",
    "        ret = []\n",
    "        for i in range(len(all_freq) - 1, -1, -1):\n",
    "            for ele in all_freq[i]:\n",
    "                for _ in range(i):\n",
    "                    ret.append(ele)\n",
    "            \n",
    "        return ''.join(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, s: str) -> str:\n",
    "        dic = dict()\n",
    "        for ch in s:\n",
    "            dic[ch] = dic.get(ch, 0) + 1\n",
    "        return sorted(s, key=lambda x: (dic[x], x), reverse=True)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
